{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #数字 1 的个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: digitOneInNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数字 1 的个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数 <code>num</code>，计算所有小于等于 <code>num</code> 的非负整数中数字 <code>1</code> 出现的个数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 0\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 13\n",
    "<strong>输出：</strong>6</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= num &lt; 10<sup>9</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>注意：本题与主站 233 题相同：<a href=\"https://leetcode-cn.com/problems/number-of-digit-one/\">https://leetcode-cn.com/problems/number-of-digit-one/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof](https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof](https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['0', '13']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, n: int) -> int:\n",
    "        high, cur, low, res, digit = n//10, n%10, 0, 0, 1\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0:\n",
    "                res += high * digit\n",
    "            elif cur == 1:\n",
    "                res += high*digit + low + 1\n",
    "            else:\n",
    "                res += (high+1)*digit\n",
    "            low += cur*digit\n",
    "            cur = high%10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = num // 10, num % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0:\n",
    "                res += high * digit\n",
    "\n",
    "            elif cur == 1:\n",
    "                res += high * digit + low + 1\n",
    "            else:\n",
    "                res += (high + 1) * digit\n",
    "\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, n: int) -> int:\n",
    "        digit = 1\n",
    "        high = n//10\n",
    "        cur = n%10\n",
    "        low = 0\n",
    "        res = 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0:\n",
    "                res += digit*high\n",
    "            elif cur ==1:\n",
    "                res += digit*high+low+1\n",
    "            else:\n",
    "                res += (high+1)*digit\n",
    "            low += cur*digit\n",
    "            cur = high%10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res\n",
    "        \n",
    "      \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        # 对于整数 num，将其所有位上 1 的出现次数相加，即为 num 中数字 1 出现的个数\n",
    "        digit = 1 #从个位开始，此时位因子为 1 \n",
    "        res = 0\n",
    "\n",
    "        # 初始化，当前位从个位开始，此时低位为 0\n",
    "        high = num // 10\n",
    "        cur = num % 10\n",
    "        low = 0\n",
    "\n",
    "        while high != 0 or cur != 0: # 当高位和当前位均为 0 才跳出循环\n",
    "            # [0 ~ high-1] [1] [0 ~ 9]\n",
    "            if cur == 0: res += high * digit\n",
    "            # [0 ~ high-1] [1] [0 ~ 9] + [high] [1] [0 ~ low]\n",
    "            elif cur == 1: res += high * digit + low + 1\n",
    "            # [0 ~ high] [1] [0 ~ 9]\n",
    "            else: res += (high + 1) * digit\n",
    "\n",
    "            low += cur * digit # 当前位从左加入到当前低位，作为下一轮计算中的低位\n",
    "            cur = high % 10 # 从当前高位的末位取出一位，作为下一轮计算中的当前位\n",
    "            high //= 10 # 当前高位排除一个末位，作为下一轮计算中的高位\n",
    "            digit *= 10 # 位因子随当前位变化\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, n: int) -> int:\n",
    "        high, cur, low, digit = n // 10, n % 10, 0, 1\n",
    "        res = 0\n",
    "        while high or cur:\n",
    "            if cur == 0:\n",
    "                res += high * digit\n",
    "            elif cur == 1:\n",
    "                res += high * digit + low + 1\n",
    "            else:\n",
    "                res += (high + 1) * digit\n",
    "            low = low + cur * digit\n",
    "            cur = high % 10\n",
    "            high = high // 10\n",
    "            digit *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        count = 0\n",
    "        factor = 1\n",
    "        n = num\n",
    "\n",
    "        while n > 0:\n",
    "            digit = n % 10\n",
    "            n //= 10\n",
    "\n",
    "            count += (n * factor)  # 对高位的贡献\n",
    "            if digit == 1:\n",
    "                count += ((num % factor) + 1)  # 对当前位的贡献\n",
    "            elif digit > 1:\n",
    "                count += factor  # 对当前位的贡献\n",
    "\n",
    "            factor *= 10\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        quotient = num // 10\n",
    "        remainder = num % 10\n",
    "        one_count = 0\n",
    "        base = 1\n",
    "        r = 0\n",
    "        \n",
    "        while quotient > 0 or remainder != 0:\n",
    "            if remainder > 1:\n",
    "                one_count += (quotient + 1) * base\n",
    "            elif remainder == 1:\n",
    "                one_count += quotient * base + r + 1\n",
    "            else:\n",
    "                one_count += quotient * base\n",
    "            \n",
    "            r = remainder * base + r\n",
    "            base *= 10\n",
    "            remainder = quotient % 10\n",
    "            quotient //= 10\n",
    "\n",
    "        return one_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        times=0\n",
    "        for i in range(0,11):\n",
    "            if num//(10**i)==0:\n",
    "                times=i-1\n",
    "                break\n",
    "        def opr(num,t):\n",
    "            if t==-1:\n",
    "                return 0\n",
    "            if t==0:\n",
    "                if num==0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return 1\n",
    "            lv=10**t\n",
    "            n=num%lv\n",
    "            m=num//lv\n",
    "            if m==0:\n",
    "                return opr(m+num,t-1)\n",
    "            if m>0:\n",
    "                if m==1:\n",
    "                    return n+1+opr(n,t-1)+t*lv//10\n",
    "                else:\n",
    "                    return lv+opr(n,t-1)+m*t*lv//10\n",
    "        \n",
    "        res=opr(num,times)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = num // 10, num % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0: res += high * digit\n",
    "            elif cur == 1: res += high * digit + low + 1\n",
    "            else: res += (high + 1) * digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, n: int) -> int:\n",
    "        res, i = 0, 1\n",
    "        while i <= n:\n",
    "            res += n // (i * 10) * i\n",
    "            x = (n // i) % 10\n",
    "            res += i if x > 1 else (n % i + 1) * x\n",
    "            i *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, n: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = n // 10, n % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0: res += high * digit\n",
    "            elif cur == 1: res += high * digit + low + 1\n",
    "            else: res += (high + 1) * digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, n: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = n // 10, n % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0: res += high * digit\n",
    "            elif cur == 1: res += high * digit + low + 1\n",
    "            else: res += (high + 1) * digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = num // 10, num % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0:\n",
    "                res += high * digit\n",
    "            elif cur == 1:\n",
    "                res += high * digit + low + 1\n",
    "            else:\n",
    "                res += (high+1)*digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        print(res)\n",
    "        return res\n",
    "\n",
    "    def digitOneInNumber_old(self, num: int) -> int:\n",
    "        s = 0\n",
    "        for i in range(num + 1):\n",
    "            s += self.count_1(i)\n",
    "        return s\n",
    "\n",
    "    def count_1(self, num):\n",
    "        s = 0\n",
    "        while num != 0:\n",
    "            if num % 10 == 1:\n",
    "                s += 1\n",
    "            num = num // 10\n",
    "        return s\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "\n",
    "        n_list = []\n",
    "        head_num = num \n",
    "        n_list.append(num % 10)\n",
    "        num = num // 10\n",
    "        while num:\n",
    "            n_list.append(num % 10)\n",
    "            num = num // 10\n",
    "        print(n_list)\n",
    "        n = len(n_list)\n",
    "        total_num = 0\n",
    "        tail_num = 0\n",
    "        for i in range(n):\n",
    "            if i > 0:\n",
    "                tail_num += n_list[i-1] * 10 **(i-1) \n",
    "            head_num = head_num // 10\n",
    "            if i < n - 1:\n",
    "                if n_list[i] == 0:\n",
    "                    total_num += 10 ** i * head_num\n",
    "                \n",
    "                elif n_list[i] == 1:\n",
    "                    total_num += 10**i * head_num + (tail_num + 1)\n",
    "\n",
    "                else:\n",
    "                    total_num += 10**i * (head_num+1)\n",
    "            else:\n",
    "                if n_list[i] == 1:\n",
    "                    total_num += (tail_num + 1)\n",
    "                else:\n",
    "                    total_num += 10**i\n",
    "\n",
    "        \n",
    "        return total_num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        s = str(num)\n",
    "\n",
    "        @cache\n",
    "        def f(i: int, cnt: int, limit: bool) -> int:\n",
    "            # 第i位，cnt个1，前面一个是否limit, 返回方案中1的个数\n",
    "            if i == len(s):\n",
    "                return cnt\n",
    "            \n",
    "            up = int(s[i]) if limit else 9  # 前面受限了，那么最高只能是s[i],否则可以到9\n",
    "            res = 0\n",
    "            for d in range(up + 1):\n",
    "                res += f(i + 1, cnt + int(d == 1), limit and d == int(s[i]))\n",
    "            return res\n",
    "\n",
    "        return f(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_first_digit(n):\n",
    "    count = 0\n",
    "    while n >= 10:\n",
    "        n = n // 10\n",
    "        count += 1\n",
    "    return n, count\n",
    "\n",
    "def backtrack(n):\n",
    "    if 1 <= n <= 9:\n",
    "        return 1\n",
    "    elif n == 0:\n",
    "        return 0\n",
    "    first_digit, n_digits = get_first_digit(n)\n",
    "    remain = n - first_digit * 10 ** n_digits\n",
    "    return backtrack(remain) + count_one_in_range(remain + 1, n, first_digit, n_digits)\n",
    "    \n",
    "def count_one_in_range(remain, n, first_digit, n_digits):\n",
    "    count = 0\n",
    "    if first_digit == 1:\n",
    "        count += n - 10 ** n_digits + 1\n",
    "    else:\n",
    "        count += 10 ** n_digits\n",
    "    count += first_digit * n_digits * 10 ** (n_digits - 1)\n",
    "    return count\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        return backtrack(num)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, n: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = n // 10, n % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0: res += high * digit\n",
    "            elif cur == 1: res += high * digit + low + 1\n",
    "            else: res += (high + 1) * digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        def process(hight,cur,low,digit):\n",
    "            if cur == 0:\n",
    "                return hight*digit\n",
    "            elif cur == 1:\n",
    "                return hight*digit + low + 1\n",
    "            elif cur > 1:\n",
    "                return (hight + 1)*digit\n",
    "        hight = num//10\n",
    "        cur = num%10\n",
    "        low = 0\n",
    "        digit = 1\n",
    "        result = 0\n",
    "        while hight > 0:\n",
    "            result += process(hight,cur,low,digit)\n",
    "            low += cur*digit\n",
    "            cur = hight%10\n",
    "            hight //= 10\n",
    "            digit *= 10\n",
    "        result += process(hight,cur,low,digit)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        base = 1\n",
    "        res = 0\n",
    "        while base <= num:\n",
    "            left = num // base // 10\n",
    "            cur = num // base % 10\n",
    "            right = num % base \n",
    "            if cur == 0:\n",
    "                res += left * base \n",
    "            elif cur == 1:\n",
    "                res += left * base + right + 1\n",
    "            else:\n",
    "                res += (left + 1) * base \n",
    "            base *= 10\n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        digit = 1\n",
    "        res = 0\n",
    "        left, current, right = num // 10, num % 10, 0\n",
    "\n",
    "        while digit <= num:\n",
    "\n",
    "            if current == 1:\n",
    "                res += left * digit + right + 1\n",
    "            elif current < 1:\n",
    "                res += left * digit\n",
    "            else:\n",
    "                res += (left+1) * digit\n",
    "            digit *= 10\n",
    "            current = left % 10\n",
    "            left = left // 10\n",
    "            right = num % digit\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = num // 10, num % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0: res += high * digit\n",
    "            elif cur == 1: res += high * digit + low + 1\n",
    "            else: res += (high + 1) * digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        base = 1\n",
    "        res = 0\n",
    "        while base <= num:\n",
    "            left = num // base // 10\n",
    "            cur = num // base % 10\n",
    "            right = num % base \n",
    "            if cur == 0:\n",
    "                res += left * base \n",
    "            elif cur == 1:\n",
    "                res += left * base + right + 1 \n",
    "            else:\n",
    "                res += (left + 1) * base \n",
    "\n",
    "            base *= 10\n",
    "        return res  \n",
    "          \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        #时间复杂度：O(longn)\n",
    "        #空间复杂度：O(1)\n",
    "        res=0\n",
    "        digit=1\n",
    "        high,cur,low=num//10,num%10,0\n",
    "        while high!=0 or cur!=0:\n",
    "            if cur==0:\n",
    "                res+=high*digit\n",
    "            elif cur==1:\n",
    "                res+=high*digit+low+1\n",
    "            else:\n",
    "                res+=(high+1)*digit\n",
    "            low=low+cur*digit\n",
    "            cur=high%10\n",
    "            high=high//10\n",
    "            digit=digit*10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, n: int) -> int:\n",
    "        a, b, one_count = 1, 10, 0\n",
    "        while n >= a:\n",
    "            x, y = divmod(n, b)\n",
    "            \n",
    "            if y >= a * 2:\n",
    "                one_count += (x + 1) * a\n",
    "            elif y >= a:\n",
    "                one_count += y + 1 + (x - 1) * a\n",
    "            else:\n",
    "                one_count += x * a \n",
    "\n",
    "            a, b = b, b*10 \n",
    "        \n",
    "        return one_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "\n",
    "        n_list = []\n",
    "        head_num = num \n",
    "        n_list.append(num % 10)\n",
    "        num = num // 10\n",
    "        while num:\n",
    "            n_list.append(num % 10)\n",
    "            num = num // 10\n",
    "        print(n_list)\n",
    "        n = len(n_list)\n",
    "        total_num = 0\n",
    "        tail_num = 0\n",
    "        for i in range(n):\n",
    "            if i > 0:\n",
    "                tail_num += n_list[i-1] * 10 **(i-1) \n",
    "            head_num = head_num // 10\n",
    "            if i < n - 1:\n",
    "                if n_list[i] == 0:\n",
    "                    total_num += 10 ** i * head_num\n",
    "                \n",
    "                elif n_list[i] == 1:\n",
    "                    total_num += 10**i * head_num + (tail_num + 1)\n",
    "\n",
    "                else:\n",
    "                    total_num += 10**i * (head_num+1)\n",
    "            else:\n",
    "                if n_list[i] == 1:\n",
    "                    total_num += (tail_num + 1)\n",
    "                else:\n",
    "                    total_num += 10**i\n",
    "\n",
    "        \n",
    "        return total_num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        s = str(num)\n",
    "        @cache\n",
    "        def dfs(i: int, cnt1: int, is_limit: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return cnt1\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up + 1):\n",
    "                res += dfs(i + 1, cnt1 + (d == 1), is_limit and d == up)\n",
    "            return res\n",
    "        return dfs(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        k, mulk = 0, 1\n",
    "        res = 0\n",
    "        while num >= mulk:\n",
    "            res += (num // (mulk * 10)) * mulk + min(max(num % (mulk * 10) - mulk + 1, 0), mulk)\n",
    "            mulk *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = num // 10, num % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0: res += high * digit\n",
    "            elif cur == 1: res += high * digit + low + 1\n",
    "            else: res += (high + 1) * digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = num // 10, num % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0: res += high * digit\n",
    "            elif cur == 1: res += high * digit + low + 1\n",
    "            else: res += (high + 1) * digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        ans = 0\n",
    "        base = 1\n",
    "        cp = 0\n",
    "        while num > 0:\n",
    "            tmp = num % 10\n",
    "            if tmp == 0:\n",
    "                ans += num // 10 * base\n",
    "            elif tmp == 1:\n",
    "                ans += num // 10 * base + cp + 1\n",
    "            else:\n",
    "                ans += (num // 10 + 1) * base\n",
    "            cp += tmp * base\n",
    "            num //= 10\n",
    "            base *= 10\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, n: int) -> int:\n",
    "        res = 0 \n",
    "        s = str(n)\n",
    "        for i, x in enumerate(s):\n",
    "            # 对应x<1时左边部分的取值\n",
    "            # 注意对于最高位而言，它的左边部分为0，这是因为最高位不可能小于1\n",
    "            left = 0 if i == 0 else int(s[0:i])\n",
    "            # 它从字符串 s 的开头（索引0）取到索引 i-1（不包括 i），将这个子字符串转换为整数。如果 i 等于 0，那么 left 将被设置为 0。\n",
    "            right = 10**(len(s)-i-1)\n",
    "            if x < \"1\":\n",
    "                res += left * right\n",
    "            elif x == \"1\":\n",
    "                extra = 1 if i == len(s) - 1 else int(s[i+1:]) + 1\n",
    "                res += left * right + extra\n",
    "            else:\n",
    "                res += (left + 1) * right\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        base = 1\n",
    "        res = 0\n",
    "        while base <= num:\n",
    "            left = num // base // 10\n",
    "            cur = num // base % 10\n",
    "            right = num % base \n",
    "            if cur == 0:\n",
    "                res += left * base \n",
    "            elif cur == 1:\n",
    "                res += left * base + right + 1 \n",
    "            else:\n",
    "                res += (left + 1) * base \n",
    "            base *= 10\n",
    "        return res  \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        str_num = str(num)\n",
    "        count = 0\n",
    "        for i in range(len(str_num)):\n",
    "            digit = int(str_num[i])\n",
    "            high = int(str_num[:i]) if i > 0 else 0\n",
    "            low = int(str_num[i+1:]) if i < len(str_num)-1 else 0\n",
    "            if digit > 1:\n",
    "                count += (high + 1) * 10 ** (len(str_num) - i - 1)\n",
    "            elif digit == 1:\n",
    "                count += high * 10 ** (len(str_num) - i - 1) + low + 1\n",
    "            else:\n",
    "                count += high * 10 ** (len(str_num) - i - 1)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = num // 10, num % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0: res += high * digit\n",
    "            elif cur == 1: res += high * digit + low + 1\n",
    "            else: res += (high + 1) * digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        #思路： \n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = num // 10, num%10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0:\n",
    "                res += high * digit\n",
    "            elif cur == 1:\n",
    "                res += high * digit + low + 1\n",
    "            else:\n",
    "                res += (high + 1) * digit\n",
    "            \n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, n: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = n // 10, n % 10, 0\n",
    "        while high!=0 or cur !=0:\n",
    "            if cur == 0:\n",
    "                res += high * digit\n",
    "            elif cur == 1:\n",
    "                res += high * digit + low + 1\n",
    "            else:\n",
    "                res += (high + 1) * digit\n",
    "            low += cur *digit\n",
    "            cur = high % 10\n",
    "            high = high // 10\n",
    "            digit = digit * 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        #时间复杂度：O(longn)\n",
    "        #空间复杂度：O(1)\n",
    "        res=0\n",
    "        digits=1\n",
    "        high,cur,low=num//10,num%10,0\n",
    "        while high!=0 or cur!=0:\n",
    "            if cur==0:\n",
    "                res+=high*digits\n",
    "            elif cur==1:\n",
    "                res+=high*digits+low+1\n",
    "            else:\n",
    "                res+=(high+1)*digits\n",
    "            low+=cur*digits\n",
    "            \n",
    "            cur=high%10\n",
    "            high=high//10\n",
    "            digits=digits*10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        k10 = 1\n",
    "        ans = 0 \n",
    "        while num >= k10:\n",
    "            ans +=  (num//(k10*10)) *k10 + min(max(0,num%( 10 * k10) - k10 + 1) ,k10)\n",
    "            k10 *= 10\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = num // 10, num % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0: res += high * digit\n",
    "            elif cur == 1: res += high * digit + low + 1\n",
    "            else: res += (high + 1) * digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res\n",
    "\n",
    "        # res = 0\n",
    "        # for i in range(1, num+1):\n",
    "        #     while i:\n",
    "        #         a = i % 10\n",
    "        #         if a==1: res += 1\n",
    "        #         i //= 10\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        ans = 0\n",
    "        base = 1\n",
    "        cp = 0\n",
    "        while num > 0:\n",
    "            tmp = num % 10\n",
    "            if tmp == 0:\n",
    "                ans += num // 10 * base\n",
    "            elif tmp == 1:\n",
    "                ans += num // 10 * base + cp + 1\n",
    "            else:\n",
    "                ans += (num // 10 + 1) * base\n",
    "            cp += tmp * base\n",
    "            num //= 10\n",
    "            base *= 10\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = num // 10, num % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0: res += high * digit\n",
    "            elif cur == 1: res += high * digit + low + 1\n",
    "            else: res += (high + 1) * digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        digit = 1\n",
    "        res = 0\n",
    "\n",
    "        while digit <= num:\n",
    "            right = num % digit\n",
    "            left = num // (digit*10)\n",
    "            current = (num - right - left*digit*10) / digit\n",
    "\n",
    "            if current == 1:\n",
    "                res += left * digit + right + 1\n",
    "            elif current < 1:\n",
    "                res += (left) * digit\n",
    "            else:\n",
    "                res += (left+1) * digit\n",
    "            digit *= 10\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        num1 = 0\n",
    "        i = 1\n",
    "        while i <= num:\n",
    "            a, b = num // i, num % i\n",
    "            num1 += (a + 8) // 10 * i + (b + 1 if a % 10 == 1 else 0)\n",
    "            i *= 10\n",
    "        return num1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        digits, res = 1, 0\n",
    "        high, cur, low = num // 10, num % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0:\n",
    "                res += high * digits\n",
    "            elif cur == 1:\n",
    "                res += high * digits + low + 1\n",
    "            else:\n",
    "                res += (high + 1) * digits\n",
    "            low += cur * digits\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digits *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "     \n",
    "        dp=[[0,0] for _ in range(12)]\n",
    "        dp[1][0] = 0\n",
    "        dp[1][1] = 1\n",
    "        for  i in range(2,12):\n",
    "            dp[i][1] = pow(10,i-1)+9*dp[i-1][0]+dp[i-1][1]\n",
    "            dp[i][0] =  9*dp[i-1][0]+dp[i-1][1]\n",
    "\n",
    "        s = str(num)\n",
    "\n",
    "        n_size = len(s)\n",
    "        res =0\n",
    "        for j in range(n_size):\n",
    "            num = int(s[j])\n",
    "            if num==1:\n",
    "                if j==n_size-1:\n",
    "                    res+=1\n",
    "                else:\n",
    "                    res+=int(s[j+1:])\n",
    "                    res+=1\n",
    "            for  k in range(num):\n",
    "                if k==1:\n",
    "                    res+=dp[n_size-j][1]\n",
    "                else:\n",
    "                    res+=dp[n_size-j][0]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        cur = num % 10 \n",
    "        high = num // 10 \n",
    "        low = 0\n",
    "        digit = 1 \n",
    "        res = 0\n",
    "        while high > 0 or cur > 0:\n",
    "            if cur == 0:\n",
    "                res += high * digit\n",
    "            elif cur == 1:\n",
    "                res += high * digit + low + 1  \n",
    "            else:\n",
    "                res += (high + 1) * digit\n",
    "            \n",
    "            low += cur * digit \n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10 \n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        s = str(num)\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def f(i, is_limit, is_num, cnt):\n",
    "            if i == n:\n",
    "                return cnt\n",
    "            res = 0\n",
    "            if is_num == 0:\n",
    "                res = f(i + 1,False,False,cnt)\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(1 - int(is_num), up + 1):\n",
    "                res += f(i + 1,is_limit and d == up, True, cnt + (d == 1))\n",
    "            return res\n",
    "        return f(0,True,False,0)           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        dp = [[0 for i in range(10)] for j in range(11)]\n",
    "        dp[1][9] = 1\n",
    "        for i in range(2, len(dp)):\n",
    "            for j in range(len(dp[0])):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = sum(dp[i-1])\n",
    "                elif j == 1:\n",
    "                    dp[i][j] = 10 ** (i-1) + dp[i][0]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][0]\n",
    "        res = 0\n",
    "        digit = len(str(num))\n",
    "        \n",
    "        while num >= 10:\n",
    "            tmp = 10 ** (digit-1)\n",
    "            index = 0\n",
    "            for i in range(0, 10):\n",
    "                index = i\n",
    "                if num - tmp < 0:\n",
    "                    break\n",
    "                else:\n",
    "                    res += dp[digit][i]\n",
    "                    num -= tmp\n",
    "            if index == 1:\n",
    "                res += num + 1\n",
    "            digit -= 1\n",
    "        if num >= 1:\n",
    "            return res + 1\n",
    "        else:\n",
    "            return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        s = str(num)\n",
    "        @cache\n",
    "        def f(i: int, cnt: int, isLimit: bool):\n",
    "            if i == len(s):\n",
    "                return cnt\n",
    "            res = 0\n",
    "            up = int(s[i]) if isLimit else 9\n",
    "            for d in range(up+1):\n",
    "                res += f(i+1, cnt + (d == 1), isLimit and d == up)\n",
    "            return res\n",
    "        return f(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitOneInNumber(self, num: int) -> int:\n",
    "        digit = 1\n",
    "        ans = 0\n",
    "        high, cur, low = num // 10, num % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0: ans += high * digit\n",
    "            elif cur == 1: ans += high * digit + low + 1\n",
    "            else: ans += (high + 1) * digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
